/* 

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 题解：https://leetcode-cn.com/problems/word-break/solution/shou-hui-tu-jie-san-chong-fang-fa-dfs-bfs-dong-tai/
// dp
const wordBreak = (s, wordDict) => {
    const wordSet = new Set(wordDict);
    const len = s.length;
    const dp = new Array(len + 1).fill(false);
    dp[0] = true;

    for (let i = 1; i <= len; i++) {
        for (let j = i - 1; j >= 0; j--) { // j去划分成两部分
            const suffix = s.slice(j, i); // 后缀部分 s[j: i-1]
            if (wordSet.has(suffix) && dp[j]) { // 后缀部分是单词，且左侧子串[0,j-1]的dp[j]为真
                dp[i] = true;
                break; // dp[i] = true了，i长度的子串已经可以拆成单词了，不需要j继续划分子串了
            }
        }
    }
    return dp[len];
}

// TS版本：
// function wordBreak(s: string, wordDict: string[]): boolean {
//     let n = s.length;
//     let wordDictSet: Set<string> = new Set(wordDict);
//     let dp: boolean[] = new Array(n + 1).fill(false);
//     dp[0] = true;

//     for (let i = 1; i <= n; i++) {
//         for (let j = 0; j < i; j++) {
//             let suffix = s.substring(j, i);
//             if (dp[j] && wordDictSet.has(suffix)) {
//                 dp[i] = true;
//                 break;
//             }
//         }
//     }

//     return dp[n];
// };